import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = new int[]{65,66,67,66,66,65,64,65,65,64};
        System.out.println(s.continuousSubarrays(nums));
    }

    public long continuousSubarrays1(int[] nums) {
        /**
         * 不间断子数组*/
        // 1 预处理
        int n = nums.length;
        int answer = n;

        // 2 循环固定窗口
        // -外层枚举窗口大小
        for(int i = 2; i <= n; i++) {
            // -2.1 创建单调队列维护区间最大值与最小值
            Deque<int[]> maxQue = new LinkedList<>();
            Deque<int[]> minQue = new LinkedList<>();
            int left = 0;
            int right = 0;
            int prev = answer;
            // -2.2 滑动固定窗口计数
            while(right < n) {
                // -1 进窗口
                // -维护最大值
                while(!maxQue.isEmpty() && maxQue.peekLast()[0] <= nums[right]) {
                    maxQue.pollLast();
                }
                maxQue.offerLast(new int[]{nums[right], right});
                // -维护最小值
                while(!minQue.isEmpty() && minQue.peekLast()[0] >= nums[right]) {
                    minQue.pollLast();
                }
                minQue.offerLast(new int[]{nums[right], right});

                // -2 判断（当区间长度满足要求时，更新）
                if(right - left + 1 == i) {
                    // -3 更新
                    if(!maxQue.isEmpty() && !minQue.isEmpty() && maxQue.peekFirst()[0] - minQue.peekFirst()[0] <= 2) {
                        answer ++;
                    }
                    // -4 出窗口（维护队头有效）
                    left ++;
                    while(!maxQue.isEmpty() && maxQue.peekFirst()[1] < left) {
                        maxQue.pollFirst();
                    }
                    while(!minQue.isEmpty() && minQue.peekFirst()[1] < left) {
                        minQue.pollFirst();
                    }
                }
                right ++;
            }
            // -2.3 小优化：若是长度为n满足条件的子数组不存在，那么长度为n+1满足条件的子数组就更不存在了，直接返回
            if(prev == answer) {
                return answer;
            }
            prev = answer;
        }

        // 3 返回值
        return answer;
    }

    public long continuousSubarrays2(int[] nums) {
        /**
         * 不间断子数组*/
        // 1 预处理
        int n = nums.length;
        int answer = 0;

        Deque<int[]> maxQue = new LinkedList<>();
        Deque<int[]> minQue = new LinkedList<>();
        int left = 0;
        int right = 0;

        // 2 修改版滑动窗口
        while(left < n) {
            // -维护最大值
            while(!maxQue.isEmpty() && maxQue.peekLast()[0] <= nums[right]) {
                maxQue.pollLast();
            }
            maxQue.offerLast(new int[]{nums[right], right});
            // -维护最小值
            while(!minQue.isEmpty() && minQue.peekLast()[0] >= nums[right]) {
                minQue.pollLast();
            }
            minQue.offerLast(new int[]{nums[right], right});

            // -固定left,当以left为起点不符合条件时，步进left回退right
            if((!maxQue.isEmpty() && !minQue.isEmpty() && maxQue.peekFirst()[0] - minQue.peekFirst()[0] > 2)) {
                left ++;
                right = left;
                maxQue = new LinkedList<>();
                minQue = new LinkedList<>();
            } else {
                // -更新值
                answer ++;
                right ++;
                // -保证right有效
                if(right == n) {
                    left ++;
                    right = left;
                    maxQue = new LinkedList<>();
                    minQue = new LinkedList<>();
                }
            }
        }

        // 3 返回值
        return answer;
    }

    public long continuousSubarrays(int[] nums) {
        /**
         * 不间断子数组
         * 思路：枚举right，找到以right为结尾的所有符合条件的子数组数目*/
        // 1 预处理
        int n = nums.length;
        long answer = 0;

        // 2 滑动窗口（固定right，维护窗口内最大值和最小值即可）
        Deque<int[]> maxQue = new LinkedList<>();
        Deque<int[]> minQue = new LinkedList<>();
        int left = 0;
        int right = 0;
        while(right < n) {
            // -1 进窗口
            // -维护最大值
            while(!maxQue.isEmpty() && maxQue.peekLast()[0] <= nums[right]) {
                maxQue.pollLast();
            }
            maxQue.offerLast(new int[]{nums[right], right});
            // -维护最小值
            while(!minQue.isEmpty() && minQue.peekLast()[0] >= nums[right]) {
                minQue.pollLast();
            }
            minQue.offerLast(new int[]{nums[right], right});

            // -2 判断 + 出窗口
            while(!maxQue.isEmpty() && !minQue.isEmpty() && maxQue.peekFirst()[0] - minQue.peekFirst()[0] > 2) {
                left ++;
                while(!maxQue.isEmpty() && maxQue.peekFirst()[1] < left) {
                    maxQue.pollFirst();
                }
                while(!minQue.isEmpty() && minQue.peekFirst()[1] < left) {
                    minQue.pollFirst();
                }
            }

            // -3 此处保证必定符合条件，计数（以right为结尾的所有子数组和，如123，就有 3、23、123，也就是他的长度）
            long k = right - left + 1;
            answer += right - left + 1;
            System.out.println("right==" + right + "时，共有" + k + "种匹配项");
            right ++;
        }

        // 3 返回值
        return answer;
    }
}
